package com.googlecode.kipler.container.graph.isomorphism;

import java.util.Comparator;
import java.util.HashMap;
import java.util.Map;

import com.googlecode.kipler.common.Copyable;
import com.googlecode.kipler.container.graph.RelationalModel;
import com.googlecode.kipler.container.graph.RelationalNode;
import com.googlecode.kipler.container.graph.RelationalValue;

public class VF2State<V extends RelationalValue<V, K>, R, K> implements
		Copyable<VF2State<V, R, K>> {
	private Map<Integer, Integer> core_1, core_2;
	private Map<Integer, Integer> in_1, in_2;
	private Map<Integer, Integer> out_1, out_2;
	private RelationalModel<V, R, K> g1, g2;
	private int t1both_len, t2both_len;
	private Comparator<RelationalNode<V, R, K>> nodeComparator;

	public VF2State(RelationalModel<V, R, K> g1, RelationalModel<V, R, K> g2,
			Comparator<RelationalNode<V, R, K>> nodeComparator) {
		this.g1 = g1;
		this.g2 = g2;
		this.nodeComparator = nodeComparator;

		core_1 = new HashMap<Integer, Integer>();
		in_1 = new HashMap<Integer, Integer>();
		out_1 = new HashMap<Integer, Integer>();
		core_2 = new HashMap<Integer, Integer>();
		in_2 = new HashMap<Integer, Integer>();
		out_2 = new HashMap<Integer, Integer>();
	}

	@Override
	public VF2State<V, R, K> copy() {
		VF2State<V, R, K> result = new VF2State<V, R, K>(g1, g2, nodeComparator);
		result.core_1 = new HashMap<Integer, Integer>(core_1);
		result.in_1 = new HashMap<Integer, Integer>(in_1);
		result.out_1 = new HashMap<Integer, Integer>(out_1);
		result.core_2 = new HashMap<Integer, Integer>(core_2);
		result.in_2 = new HashMap<Integer, Integer>(in_2);
		result.out_2 = new HashMap<Integer, Integer>(out_2);
		result.t1both_len = t1both_len;
		result.t2both_len = t2both_len;
		return result;
	}

	public boolean isGoal() {
		return (core_2.size() == g2.size());
	}

	public void addPair(Pair pair) {
		int nI = pair.getLeft();
		int mI = pair.getRight();
		int core_len = core_1.size();

		if (!in_1.containsKey(nI)) {
			in_1.put(nI, core_len);
			if (out_1.containsKey(nI))
				t1both_len++;
		}
		if (!out_1.containsKey(nI)) {
			out_1.put(nI, core_len);
			if (in_1.containsKey(nI))
				t1both_len++;
		}
		if (!in_2.containsKey(mI)) {
			in_2.put(mI, core_len);
			if (out_2.containsKey(mI))
				t2both_len++;
		}
		if (!out_2.containsKey(mI)) {
			out_2.put(mI, core_len);
			if (in_2.containsKey(mI))
				t2both_len++;
		}

		core_1.put(nI, mI);
		core_2.put(mI, nI);

		RelationalNode<V, R, K> n = g1.getNode(nI);
		RelationalNode<V, R, K> m = g2.getNode(mI);

		for (RelationalNode<V, R, K> nPrime : n.getOutgoing()) {
			int nPrimeI = g1.getIndex(nPrime);
			if (!out_1.containsKey(nPrimeI)) {
				out_1.put(nPrimeI, core_len);
				if (in_1.containsKey(nPrimeI)) {
					t1both_len++;
				}
			}
		}

		for (RelationalNode<V, R, K> nPrime : n.getIncoming()) {
			int nPrimeI = g1.getIndex(nPrime);
			if (!in_1.containsKey(nPrimeI)) {
				in_1.put(nPrimeI, core_len);
				if (out_1.containsKey(nPrimeI)) {
					t1both_len++;
				}
			}
		}

		for (RelationalNode<V, R, K> mPrime : m.getOutgoing()) {
			int mPrimeI = g2.getIndex(mPrime);
			if (!out_2.containsKey(mPrimeI)) {
				out_2.put(mPrimeI, core_len);
				if (in_2.containsKey(mPrimeI)) {
					t2both_len++;
				}
			}
		}

		for (RelationalNode<V, R, K> mPrime : m.getIncoming()) {
			int mPrimeI = g2.getIndex(mPrime);
			if (!in_2.containsKey(mPrimeI)) {
				in_2.put(mPrimeI, core_len);
				if (out_2.containsKey(mPrimeI)) {
					t2both_len++;
				}
			}
		}
	}

	public Pair nextPair(Pair prev) {
		int n, m;
		int t1out_len = out_1.size();
		int t2out_len = out_2.size();
		int t1in_len = in_1.size();
		int t2in_len = in_2.size();
		int core_len = core_1.size();

		if (prev.equals(Pair.initial())) {
			n = 0;
			m = 0;
		} else {
			n = prev.getLeft() + 1;
			m = prev.getRight();
		}

		if (t1both_len > core_len && t2both_len > core_len) {
			while (m < g2.size()
					&& (core_2.containsKey(m) || !out_2.containsKey(m) || !in_2
							.containsKey(m))) {
				m++;
				n = 0;
			}
		} else if (t1out_len > core_len && t2out_len > core_len) {
			while (m < g2.size()
					&& (core_2.containsKey(m) || !out_2.containsKey(m))) {
				m++;
				n = 0;
			}
		} else if (t1in_len > core_len && t2in_len > core_len) {
			while (m < g2.size()
					&& (core_2.containsKey(m) || !in_2.containsKey(m))) {
				m++;
				n = 0;
			}
		} else {
			while (m < g2.size() && core_2.containsKey(m)) {
				m++;
				n = 0;
			}
		}

		if (t1both_len > core_len && t2both_len > core_len) {
			while (n < g1.size()
					&& (core_1.containsKey(n) || !out_1.containsKey(n) || !in_1
							.containsKey(n))) {
				n++;
			}
		} else if (t1out_len > core_len && t2out_len > core_len) {
			while (n < g1.size()
					&& (core_1.containsKey(n) || !out_1.containsKey(n))) {
				n++;
			}
		} else if (t1in_len > core_len && t2in_len > core_len) {
			while (n < g1.size()
					&& (core_1.containsKey(n) || !in_1.containsKey(n))) {
				n++;
			}
		} else {
			while (n < g1.size() && core_1.containsKey(n)) {
				n++;
			}
		}

		Pair result = null;
		if (n < g1.size() && m < g2.size()) {
			result = new Pair(n, m);
		}

		return result;
	}

	public boolean isFeasiblePair(Pair p) {
		int termout1 = 0, termout2 = 0, termin1 = 0, termin2 = 0, new1 = 0, new2 = 0;

		RelationalNode<V, R, K> n = g1.getNode(p.getLeft());
		RelationalNode<V, R, K> m = g2.getNode(p.getRight());

		if (nodeComparator.compare(n, m) != 0) {
			return false;
		}
		// the out edges of n
		for (RelationalNode<V, R, K> nPrime : n.getOutgoing()) {
			int nPrimeI = g1.getIndex(nPrime);
			if (core_1.containsKey(nPrimeI)) {
				int mPrimeI = core_1.get(nPrimeI);
				RelationalNode<V, R, K> mPrime = g2.getNode(mPrimeI);
				if (!m.containsOutgoing(mPrime)
						|| !n.edgesOutgoing(nPrime).containsAll(
								m.edgesOutgoing(mPrime))) {
					return false;
				}
			} else {
				if (in_1.containsKey(nPrimeI))
					termin1++;
				if (out_1.containsKey(nPrimeI))
					termout1++;
				if (!in_1.containsKey(nPrimeI) && !out_1.containsKey(nPrimeI))
					new1++;
			}
		}

		// the in edges of n
		for (RelationalNode<V, R, K> nPrime : n.getIncoming()) {
			int nPrimeI = g1.getIndex(nPrime);
			if (core_1.containsKey(nPrimeI)) {
				int mPrimeI = core_1.get(nPrimeI);
				RelationalNode<V, R, K> mPrime = g2.getNode(mPrimeI);
				if (!m.containsIncoming(mPrime)
						|| !n.edgesIncoming(nPrime).containsAll(
								m.edgesIncoming(mPrime))) {
					return false;
				}
			} else {
				if (in_1.containsKey(nPrimeI))
					termin1++;
				if (out_1.containsKey(nPrimeI))
					termout1++;
				if (!in_1.containsKey(nPrimeI) && !out_1.containsKey(nPrimeI))
					new1++;
			}
		}

		// the out edges of m
		for (RelationalNode<V, R, K> mPrime : m.getOutgoing()) {
			int mPrimeI = g2.getIndex(mPrime);
			if (core_2.containsKey(mPrimeI)) {
				int nPrimeI = core_2.get(mPrimeI);
				RelationalNode<V, R, K> nPrime = g1.getNode(nPrimeI);
				if (!n.containsOutgoing(nPrime)) {
					return false;
				}
			} else {
				if (in_2.containsKey(mPrime))
					termin2++;
				if (out_2.containsKey(mPrime))
					termout2++;
				if (!in_2.containsKey(mPrime) && !out_2.containsKey(mPrime))
					new2++;
			}
		}

		// the in edges of m
		for (RelationalNode<V, R, K> mPrime : m.getIncoming()) {
			int mPrimeI = g2.getIndex(mPrime);
			if (core_2.containsKey(mPrimeI)) {
				int nPrimeI = core_2.get(mPrimeI);
				RelationalNode<V, R, K> nPrime = g1.getNode(nPrimeI);
				if (!n.containsIncoming(nPrime)) {
					return false;
				}
			} else {
				if (in_2.containsKey(mPrime))
					termin2++;
				if (out_2.containsKey(mPrime))
					termout2++;
				if (!in_2.containsKey(mPrime) && !out_2.containsKey(mPrime))
					new2++;
			}
		}

		return termin1 >= termin2 && termout1 >= termout2 && new1 >= new2;
	}
}
